#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<map>
#include<bitset>
using namespace std;
template<class K>
class ufs
{
	//用来映射存储数据，和集合
	//存储森林
	//森林的值不一定是整形
	vector<int> arr;
	//用来映射对应的元素
	map<K, int> order_map;
	vector<K> get;
public:
	template<class InputIterator>
	ufs(InputIterator begin,InputIterator end)
	{
		//定义一共多少数据
		auto it = begin;
		int key = 0;
		while (it != end)
		{
			arr.push_back(-1);
			get.push_back(*it);
			order_map[*it] = key++ ;

			it++;
		}
	}
	//找到根节点
	K find_root(K tem)
	{
		//就是根据数组进行遍历
		if (!order_map.count(tem))
		{
			return K();
		}
		int or1 = order_map[tem];
		while (arr[or1 ] >= 0)
		{
			or1 = arr[or1 ];
		}
		return get[arr[or1]] ;
	}
	//

	bool link(K tem1, K tem2)
	{
		if (!order_map.count(tem1) || tem1 == tem2)
		{
			return false;
		}
		int k1 = order_map[find_root(tem1)];
		int k2 = order_map[find_root(tem2)];
		int root = max(k1, k2);
		int opt = min(k1, k2);
		arr[opt] = root;
		arr[root]--;
		return false;
	}
	size_t amount()
	{
		size_t cnt = 0;
		for (auto i : arr) 
			if(i <0)
				cnt++;
		return cnt;
	}
	~ufs()
	{}
};
int main()
{
	
	int arr[] = { 1,2,3,4,6 };
	ufs<int> te(arr,arr + 5);
	int i = 1;
	int j = 2;
	bitset<30> tem;
	for (auto c : arr)
	{
		if (c % 2)
		{
			te.link(i, c);
			i = c;

		}
		else
		{
			te.link(j, c);
			j = c;
		}
	}
	return 0;
}